rtk 2018

2018.1.1 - dopolni

Collatz++

1. podnaloga

Collatzevo zaporedje je zaporedje naravnih števil, v katerem je vsak člen izračunan iz prejšnjega po naslednjem pravilu: če je prejšnji člen — recimo mu $n$ — deljiv z $2$, je naslednji člen enak $n/2$, sicer pa je naslednji člen enak $3n + 1$. Ustavimo se, ko pridemo do števila $1$.

Konkretno zaporedje, ki ga na ta način dobimo, je odvisno od tega, s katerim številom začnemo. Na primer, Collatzevo zaporedje z začetnim členom $15$ je: $15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1$. Gojmir je napisal funkcijo, ki poišče takšno število $k$ z območja od vključno $a$ do vključno $b$, da Collatzevo zaporedje z začetkom k nekje doseže maksimalno vrednost. Npr. na območju od $30$ do $50$ je takšno število $k = 31$, saj je pripadajoče zaporedje: $31, 94, 47, 142, 71, 214, . . . , 6154, 3077, 9232, 4616, 2308, 1154, . . . , 5, 16, 8, 4, 2, 1$. To zaporedje doseže maksimum $9232$. Če izberemo kot začetni člen katerokoli drugo celo število z območja od $30$ do $50$, tega ne bomo presegli.

Kmalu pa je opazil, da ima njegova funkcija pomanjkljivost, saj $k = 41$ prav tako doseže enak maksimum. Ker je izčrpan in ne more več programirati, potrebuje tvojo pomoč.

Poleg tega pa je Gojmirova datoteka ob prenosu utrpela nekaj poškodb, zaradi česar v programu manjkajo vsi komentarji in nekaj kode (označeno z ###)

def poisci_vse(a, b):
   naj = 0
   v = [ ]
   for k in range(a, b + 1):
       n = kNaj = k
       while n != 1:
           n = n // 2 if n % 2 == 0 else 3 * n + 1
           if n > kNaj:
               ###
       if kNaj > naj:
             ###
             naj = ###
       if ### == ###: v.append(k)
  return ###

Naloga

Dopolni funkcijo poisci_vse(a, b).

Vhodni podatki

Parametra funkcije sta celi števili $a < b$, ki sta meji območja, kjer iščeš maksimume v Collatzovemu zaporedju.

>>> poisci_vse(30,50)

Izhodni podatki

Tabela z začetnimi členi, ki dosežejo maksimum.

[31,41,47]

Primer

poisci_vse(30, 50) mora najti števila $31$, $41$ in $47$ — če se namreč Collatzevo zaporedje začne z enim od teh treh števil, bo sčasoma doseglo vrednost $9232$; in te vrednosti ne bo nikoli doseglo (ali preseglo), če se začne s katerimkoli drugim številom od $30$ do $50$.

Uradna rešitev

def poisci_vse(zacetek_intervala, konec_intervala):
    '''Poišče in vrne začetne člene med a in b,
    pri katerih je dosežen maksimum v collatzevem zaporedju '''
    naj_vrednost = 0
    seznam_zacetnih_clenov = []
    for zacetni_clen in range(zacetek_intervala, konec_intervala + 1):
        collatzev_clen = max_collatzev_clen = zacetni_clen
        while collatzev_clen != 1: # zaženemo Collatzevo zaporedje
            collatzev_clen = collatzev_clen // 2 if collatzev_clen % 2 == 0 else 3 * collatzev_clen + 1
            if collatzev_clen > max_collatzev_clen:
                max_collatzev_clen = collatzev_clen # vsakič ko presežemo max vrednost zabeležimo novo
        if max_collatzev_clen > naj_vrednost:
            seznam_zacetnih_clenov.clear()
            naj_vrednost = max_collatzev_clen # če imamo najboljšo rešitev jo shranimo
        if max_collatzev_clen == naj_vrednost:
            seznam_zacetnih_clenov.append(zacetni_clen) # če imamo enako dobro rešitev jo dodamo
    return seznam_zacetnih_clenov

2018.1.2 - dopolni

Alfa Bravo

1. podnaloga

Palček Godrnjavček je postal vodja tajne službe, ki skrbi za varnost Sneguljčice, njegova naloga pa je, da sprejema podatke agentov na terenu in jim daje navodila, kako naj ukrepajo. Da bi se palčki zaščitili pred napakami pri sporazumevanju, so uvedli fonetično abecedo, ki posamezni črki priredi besedo.

A...ALFA          J...JULIET        R...ROMEO
B...BRAVO         K...KILO          S...SIERRA
C...CHARLIE       L...LIMA          T...TANGO
D...DELTA         M...MIKE          U...UNIFORM
E...ECHO          N...NOVEMBER      V...VICTOR
F...FOXTROT       O...OSCAR         W...WHISKY
G...GOLF          P...PAPA          X...X-RAY
H...HOTEL         Q...QUEBEC        Y...YANKEE
I...INDIA                           Z...ZULU

Godrnjavček te prosi, da dopolniš njegovo funkcijo, ki bo znala vnešeno besedilo odkodirati. Napisal je večino funkcije dekodiraj(dat), manjka pa mu nekaj kode. Prav tako ni znal napisati funkcije se_ujema(beseda, koda), ki preveri, s katero črko se ujema dana koda.

def dekodiraj(dat):
    niz = ''
    sporocilo = open(dat,'r',encoding='utf-8')
    for ### in ###:
        for ### in vrstica.split():
            for c in range(len(kode)):
                if se_ujema(###, ###):
                    niz += (chr(ord('A') + c))
                    break
    return ###

Pri tem naj bo funkcija odporna tudi na manjše napake pri kodiranju: namesto prave kodne besede se lahko v vhodnih podatkih pojavi taka beseda, ki se od prave razlikuje v največ enem znaku (je pa zagotovo še vedno enako dolga kot prava kodna beseda).

Tako se lahko na primer zgodi, da namesto besede LIMA dobimo RIMA ali LINA ali LQMA in tako naprej, vse te besede pa ravno tako predstavljajo črko L.

Naloga

Dopolni funkcijo dekodiraj(dat), ki sprejme tekstovno datoteko in vrne niz z dekodiranim sporočilom. Morda je smiselno definirati še dodatno funkcijo, ki preveri, za katero zakodirano črko gre. Napiši pomožno funkcijo se_ujema(beseda, koda), ki preveri, s katero črko se ujema dana koda.

Vhodni podatki

Tekstovna datoteka z zakodiranim sporočilom z napakami:

SIERRA
RODEO
ERHO
CHARLIF
MOVEMBER
OSQAR

Izhodni podatki

Niz z dekodiranim sporočilom

"SRECNO"

Komentar

Na tekmovanju je bilo možno izbirati med branjem s standardnega vhoda in branjem z datoteke.

Uradna rešitev

kode = ["ALFA", "BRAVO", "CHARLIE" , "DELTA", "ECHO","FOXTROT","GOLF","HOTEL","INDIA","JULIET",
        "KILO","LIMA","MIKE","NOVEMBER","OSCAR","PAPA","QUEBEC","ROMEO","SIERRA","TANGO","UNIFORM",
        "VICTOR","WHISKY","X-RAY","YANKEE","ZULU"]
def se_ujema(beseda, koda):
    '''Funkcija preveri, ali se dana beseda ujema s kodo (z največ 1 napako)
     in vrne True ali False'''
    dolzina_besede = len(beseda)
    st_neujemanj = 0
    if len(koda) != dolzina_besede:
        return False
    for i in range(dolzina_besede):
        if beseda[i] == koda[i]:
            continue
        st_neujemanj += 1
        if st_neujemanj > 1:
            return False
    return True

def dekodiraj(dat):
    '''Funkcija pretvori zakodirano sporočilo v datoteki v nam razumljivo,
       jo shrani v niz in vrne.'''
    dekodirana_beseda = ''
    sporocilo = open(dat,'r',encoding='utf-8')
    for vrstica in sporocilo:
        for beseda in vrstica.split():
            for znak in range(len(kode)):
                if se_ujema(beseda, kode[znak]):
                    dekodirana_beseda += (chr(ord('A') + znak))
                    break
    sporocilo.close()
    return dekodirana_beseda

2018.1.3 - dopolni

Sestavljanka

1. podnaloga

Gojmir je na polici opazil škatlo s sestavljanko, ki ima $136$ koščkov. Gojmir ve, da sestavljanko dobimo tako, da sliko razrežemo s (skoraj) vodoravnimi in (skoraj) navpičnimi črtami, tako da dobimo (skoraj) kvadratne koščke. Opazil pa je, da slika, ki jo tvori sestavljanka, v resnici ni kvadratna. Takole čez palec je ocenil, da je razmerje med višino in širino slike približno $3 : 7$.

Koliko koščkov v resnici pride po višini in koliko po širini? Pravokotnik iz $136$ koščkov bi lahko bil oblike $1×136$ ali $2×68$ ali $4×34$ ali $8×17$ in tako naprej.

Vprašanje je torej, pri katerem od teh pravokotnikov je razmerje med višino in širino najbližje tistemu, ki ga je ocenil Gojmir.

Gojmir je že spisal del funkcije, ki to izračuna v splošnem. Vendar mu ni uspelo kode dokončati. (manjkajoči deli označeni z ###)

def sestavljanka(st_kosov, razmerje):
    for h in range(1, st_kosov + 1):
        if ### != 0:
            continue
        priblizek = ###
        razlika = ###(h / priblizek - razmerje)
        if ### == 1 or razlika < ###:
            naj_visina = h
            min_razlika = razlika
    return (naj_visina, st_kosov // naj_visina)

Naloga

Dopolni funkcijo sestavljanka(st_kosov, razmerje), ki bo to izračunala v splošnem primeru, za poljubno število koščkov in poljubno razmerje. Gojmir določi razmerje višine in širine dokaj natančno, vendar ne povsem natančno.

Vhodni podatki

Parametra funkcije sta število koščkov (naravno število) in razmerje (realno število).

>>> sestavljanka(136, 0.428)

$(3/7 ≈ 0.428)$

Izhodni podatki

Funkcija mora vrniti par

(8 , 17)

(8 vrstic, 17 stolpcev). Pri tej sestavljanki je razmerje med višino in širino enako $8/17 ≈ 0,471$, kar je od vseh možnih pravokotnih sestavljank s $136$ koščki najbližje iskanemu razmerju $0,428$.

Uradna rešitev

def sestavljanka(st_kosov, razmerje):
    '''Izračuna in vrne tisti približek za razmerje višina:širina,
    ki je najbljižje razmerju '''
    for h in range(1, st_kosov + 1):
        if st_kosov % h != 0:
            continue
        priblizek = st_kosov // h
        razlika = abs(h / priblizek - razmerje)
        if h == 1 or razlika < min_razlika:
            naj_visina = h
            min_razlika = razlika
    return (naj_visina, st_kosov // naj_visina)

2018.1.5 - dopolni

Brzinomer

1. podnaloga

V avtomobilu za prikaz trenutne hitrosti vozila skrbi instrument (brzinomer), ki je lahko digitalen (prikazuje številke) ali pa analogen (fizični kazalec instrumenta se pomika po skali in s svojo lego kaže izmerjeno hitrost).

A tudi prikazovalniki s kazalcem in skalo so doživeli svojo prenovo in niso več preprosti analogni merilniki neke fizikalne veličine, ampak gre za prikazovalnike, kjer je kazalec pritrjen na os miniaturnega koračnega elektromotorčka, pomike tega pa krmili avtomobilski računalnik glede na hitrost, ki jo izmerijo tipala hitrosti.

Naš prikazovalnik ima skalo v obsegu od $0 km/h$ do $250 km/h$. Koračni motorček lahko pomika kazalec v vsakem koraku le za $1 km/h$ navzgor ali navzdol, ali pa kazalca ne premakne. Če je kazalec že v najnižji legi, ukaz za pomik navzdol ne stori ničesar (kazalec ostane v najnižji legi, t.j. kaže na $0 km/h$ na skali). Podobno tudi pri najvišji legi: ukaz za pomik navzgor ne stori ničesar, kazalec ostane pri najvišji legi, t.j. kaže na $250 km/h$ na skali.

Premik koračnega motorčka za en korak (oz. kazalca, pritrjenega nanj, za $1 km/h$) je sicer precej hiter, vendar vseeno zahteva določen čas. Da ne bi avtomobilski računalnik skušal premikati kazalca hitreje, kot to koračni motorček zmore, skrbi ura, ki se proži nekajkrat v sekundi in jamči, da je takrat koračni motorček pripravljen sprejeti nov ukaz za pomik za en korak.

Naloga

Max = 250
kazalec = 0
zacetek = Max
def premik(hitrost):
    global kazalec, zacetek
    if ### > 0: zacetek -= 1; return ###
    if ### > Max: hitrost = Max
    premik = ### if hitrost > kazalec else ### if hitrost < kazalec else ###
    kazalec ### premik
    return premik

Dopolni funkcijo premik(hitrost) (označeno z ###), ki jo bo ura periodično klicala (približno stokrat v sekundi, točna vrednost intervala ni pomembna). Kot argument bo funkcija ob vsakem klicu prejela celo število med $0$ in $300$, ki predstavlja trenutno hitrost avtomobila v $km/h$.

Glede na svoje vedenje o trenutni legi kazalca brzinomera naj funkcija vrne vrednost $−1$, $+1$ ali $0$, kar bo povzročilo pomik kazalca za en korak navzdol ali navzgor ali pa pomika v tem časovnem intervalu ne bo. Funkcija naj skrbi, da bo lega kazalca brzinomera čim bolj verno sledila dejanski hitrosti avtomobila.

Upoštevaj, da se lahko hitrost avtomobila med dvema zaporednima klicema tvoje funkcije spremeni tudi za več kot $1 km/h$. V tem primeru bo sicer kazalec merilnika lahko za krajši čas zaostajal s pravim prikazom, a mora pravo lego po najboljših močeh čim prej ujeti. Pri hitrostih nad prikazovalnim območjem (t.j. nad $250 km/h$) naj kazalec tiči v svoji najvišji legi. Po potrebi lahko deklariraš poljubne globalne spremenljivke in jim tudi določiš začetne vrednosti.

Upoštevaj tudi, da ob zagonu avtomobilskega računalnika ne vemo točno, kje je obtičal kazalec brzinomera — lahko bi se npr. zgodilo, da je bil motor avtomobila (in računalnik) ugasnjen, še preden se je avtomobil dokončno ustavil na domačem dvorišču. Da zagotovimo znano lego kazalca, si lahko pomagamo z informacijo iz drugega odstavka, ki zagotovi, da z $250$ koraki navzdol zagotovo dosežemo spodnjo lego (torej prikaz $0 km/h$) ne glede na začetni položaj kazalca. Za pravilno testiranje zato uporabi

for i in range(251):
    premik(250)

ko napišeš funkcijo.

Uradna rešitev

Max = 250
kazalec = 0
zacetek = Max
def premik(hitrost):
    '''Premakne kazalec za 1 naprej, če je hitrost povečana in nazaj
       če je zmanjšana.'''
    global kazalec, zacetek
    if zacetek > 0:
        zacetek -= 1
        return -1
    if hitrost < 0:
        hitrost = 0
    if hitrost > Max:
        hitrost = Max
    if hitrost > kazalec:
        premik = 1
    elif hitrost < kazalec:
        premik = -1
    else:
        premik = 0
    kazalec += premik
    return premik